\documentclass[a4paper,10pt]{article}

\usepackage[utf8]{inputenc}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float} 
\usepackage{ctable}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsfonts}
\usepackage{cite}
\usepackage[]{algorithm2e}

\usepackage{fullpage}

\usepackage{listings}
\lstset{breaklines=true} 


\def\th{^{th}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\pop}{\mathcal{P}}

\def\th{^{th}}
\def\pd{\frac{\partial}{\partial q_i^k}}
\newcommand{\mcf}[1]{p\Big( \norm{\bs{#1}^k}_1 \Big)}
\def\pdy{\frac{\partial}{\partial y_i^k}}
\def\pdq{\frac{\partial}{\partial q_i^k}}
\newcommand{\diag}{\mathop{\mathrm{diag}}}
%\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

\newcommand{\normb}[1]{\left\lVert \bs{#1} \right\rVert_1}


\usepackage{autonum}
\usepackage{placeins}

\title{Population Dynamics Toolbox}
\author{Carlos Barreto}

\begin{document}
\lstset{language=Matlab} 
\maketitle



\begin{abstract}
 The \emph{population dynamics toolbox} (PDToolbox) contains a set of functions to implement evolutionary dynamics with multiple populations. We consider both small and large populations. For finite populations, we implement some revision protocols to model random interactions between agents. On the other hand, the evolution of a society with large populations is approximated by dynamical equations. 
 
 This toolbox is designed to facilitate the implementation of any game with different evolutionary dynamics or revision protocols.  In particular, our attempt is to make an efficient implementation of the algorithms to compute the dynamical evolution of the society. Also, the toolbox counts with some functions to plot the state of the system and the evolution of each strategy.
 
 In Section \ref{sec:introduction} we start by introducing the notation used along the paper and we present some ideas of population games which lead to the \emph{mean dynamics} equation. In Section \ref{sec:protocols} we introduce some well known revision protocols and evolutionary dynamics. In Section \ref{sec:implementation} we introduce some details of the implementation of games with the toolbox and show an example of the implementation of the rock-paper-scissors game.
 Sections \ref{sec:combined} and \ref{sec:multi-pop} contain examples of the implementation of \emph{combined dynamics} and \emph{multi-population games}.
 
\end{abstract}


\tableofcontents



\input{introduction}
 
\input{evolutionary_dynamics} 

\input{implementation} 

\input{combined_dynamics}

\input{multipopulation}

\input{maximization}

\input{example_dr}



 \FloatBarrier
\section{Running Time Analysis}\label{sec:running_time}


In this section we investigate the running time of the evolutionary dynamics as a function of either the number of populations or the number of strategies per population. We use the demand response example from Section \ref{sec:dr_example} to make the experiments.
Our interest is to observe the time that takes to simulate the evolution of the dynamics during 10 seconds.

\subsection{Running Time as a Function of the Number of Populations}

Note that the time complexity of the algorithms, with respect to number of populations $P$, is $O(P \cdot T_f(n,P))$. The fitness function in the example satisfies $T_f(n,P)=O(nP)$. Hence, the complexity of the dynamics with respect to $P$ is $O(P^2)$. 

Although the dynamics have the same time complexity, the running time of the dynamics has substantial differences. 
Fig. \ref{fig:run_time_pop} shows the running time of the game for multiple number of populations. In this case each population has $24$ strategies and all populations have the same set of fitness functions. 
From the simulations we observe that the 
%running time increases roughly linearly for all dynamics. The 
fastest simulations are made with replicator dynamics. 
Moreover, there is a large difference between the running time of Replicator and the other dynamics.
%On the other hand, Smith and Logit dynamics have almost the same running time. 
%
One reason is that the ODE solver run less iterations with Replicator dynamics, and consequently, it makes less calls to the dynamic's algorithm. 



\subsection{Running Time as a Function of the Number of Strategies}


Fig. \ref{fig:run_time_str} shows the running time of the game for different number of strategies per population. In this case we  define $25$ populations. Note that the time complexity of the dynamics with respect to the number of strategies is $O(n)$ (or $O(n \log n)$ in the case of the Smith dynamics). In this case Replicator has the lowest running time, while smith have the largest running time. The large difference between Smith and the other dynamics is that the ODE solver makes much more iterations.


Note that, except for Smith dynamics, the running time is lower when we implement games with large number of strategies. Hence, the maximization problem in Section \ref{sec:maximization} might be solved faster using the single population case.



\begin{figure}
        \centering
        \begin{subfigure}[b]{0.45\textwidth}
		\includegraphics[width=1\textwidth]{./images/running_time_pop.eps}
                \caption{Run time for different population numbers and constant number of strategies.}
                \label{fig:run_time_pop}
        \end{subfigure}
        ~ 
        \begin{subfigure}[b]{0.45\textwidth}
		\includegraphics[width=1\textwidth]{./images/running_time_str.eps}
		%\includegraphics[width=1\textwidth]{./images/running_time_strategies.eps}
                \caption{Run time for different number  of strategies and constant number of populations.}
                \label{fig:run_time_str}
        \end{subfigure}
        \caption{Run time of four evolutionary dynamics: `rd', `bnn', `smith', and `logit'.}
        \label{fig:run_time}
\end{figure}

%Which case gives the largest simulation time?



\subsection{Running Time of Smith Dynamics }

In the toolbox we include two algorithms for the Smith dynamics. One of them relies on matrix multiplications and has running time $O(P(T_f(n,P) + n^2))$ (`smith.m'), while the other has time complexity $O(P(T_f(n,P) + n \log n))$ (`smith\_b.m'). Even though the time complexity of the first algorithm is higher, its simulation are faster under certain conditions. The reason is that Matlab is optimized to work with matrices. From the experiments we see that  `smith\_b.m' is faster only for large number strategies (see Fig. \ref{fig:smith_run_time}).

\begin{figure}
        \centering
        \begin{subfigure}[b]{0.45\textwidth}
                \includegraphics[width=\textwidth]{./images/running_time_smith_pop.eps}
                \caption{Run time for different population numbers and constant number of strategies.}
                \label{fig:smith_run_time_pop}
        \end{subfigure}%
        ~ 
        \begin{subfigure}[b]{0.45\textwidth}
                \includegraphics[width=\textwidth]{./images/running_time_smith_str.eps}
                \caption{Run time for different number  of strategies and constant number of populations.}
                \label{fig:smith_run_time_str}
        \end{subfigure}%

        \caption{Run time of two implementations of the Smith dynamics, namely `smith' and `smith\_b'.}
        \label{fig:smith_run_time}
\end{figure}


 \FloatBarrier





\iffalse

 \FloatBarrier
 
\section{Designing games}

In the previous section we show some examples of strategical situations that can be analyzed with game theory. In these cases, the structure of the game is given by the problem. However, we can modify the fitness function of each player in order to solve an optimization problem.

For example, let us consider the following optimization problem:

\begin{equation}\label{eq:opt_problem}
\begin{aligned}
& \underset{x}{\text{maximize}} 
& & \sum_{i=1}^N U_i(x_i)  - C(|x|)\\
& \text{subject to}
& & 0 \leq q_i \geq m,  i =\{1,\ldots, N\}.
\end{aligned}
\end{equation}

This can be seen as a problem of allocating a finite resource to maximize a utility function. 

Note that there are $N$ agents with that give a valuation $v_i(x_i)$ to the resource $x_i$.

However, the cost of assigning the resource is $C(|x|)$ .

The cost of assigning the resource might be distributed among the population. 

Let us consider the following example:


\begin{equation}
U_i(x_i) =   \alpha_i  log(1+x_i) 
\end{equation}

\begin{equation}
C(z) = \beta z^2 + b z 
\end{equation}

define fitness functions as 

\begin{equation}
f_i(x_1, x_2) = \frac{\alpha_i}{1+x_i} - 2 \beta |x| - b 
\end{equation}

\fi


--



\bibliographystyle{plain}
\bibliography{references}



\end{document}



\iffalse


      
\begin{figure}[htb]
 \includegraphics[1\textwidth]{./images/}
 \caption{}
 \label{fig:}
\end{figure}



\fi
